package Day01;

/**
 * 快排模板
 * 分界点是 随机的数组里面的一个值
 */
public class QuickSort {

    public static void quickSort(int[] arr, int l, int r) {
        // 判断边界条件
        if (l >= r) {
            return;
        }
        int x = arr[l];
        int i = l - 1;
        int j = r + 1;
        while (i < j) {
            // 初始位置 i 指向开头位置 ， j 指向结尾位置
            do {
                i++;
            } while (arr[i] < x);
            do {
                j--;
            } while (arr[j] > x);
            if (i < j) {
                swap(arr, i, j);
            }
            quickSort(arr, l, j);
            quickSort(arr, j + 1, r);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }



    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 1, 8, 6};
        quickSort(arr,0,4);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }


}
